#include "myfunc.h"

void GetTuple(struct Tuple *tuple, int pos, unsigned char *blk)
{
    int i;
    char str[5];
    for (i = 0; i < 4; i++)
    {
        str[i] = *(blk + pos * 8 + i);
    }
    tuple->first = atoi(str);
    for (i = 0; i < 4; i++)
    {
        str[i] = *(blk + pos * 8 + i + 4);
    }
    tuple->second = atoi(str);
}

int Compare(const char *a, const char *b)
{
    int i;
    char str_a[5], str_b[5];
    for (i = 0; i < 4; i++)
    {
        str_a[i] = *(a + i);
        str_b[i] = *(b + i);
    }
    const int aa = atoi(str_a);
    const int bb = atoi(str_b);
    return (aa > bb) - (aa < bb);
}
void FindMin(struct MergeInfo *info, int num, int *cur_min, int *cur_pos)
{
    int i;
    *(cur_min) = 100;
    for (i = 1; i <= num; i++)
    {
        if (info[i].valid > 0 && info[i].cur_head < *cur_min)
        {
            *cur_min = info[i].cur_head;
            *cur_pos = i;
        }
    }
}
// merge 8 sorted blocks from start
void Merge_8(int start, int *IO)
{
    int i, j = 1;
    int cur_min, cur_pos;
    int valid_num = 8;
    Buffer buf, buf_write;
    struct Tuple tuple;
    struct MergeInfo info[9]; // 硬盘地址从1开始，定义9个避免混淆
    initBuffer(520, 64, &buf);
    initBuffer(72, 64, &buf_write);

    // use info[0] to store write data
    info[0].blk = getNewBlockInBuffer(&buf_write);
    info[0].scan_pos = 0;
    for (i = 1; i <= 8; i++)
    {
        info[i].blk = readBlockFromDisk(start + i, &buf);
        info[i].scan_pos = 1;
        info[i].valid = 1;
        GetTuple(&tuple, 0, info[i].blk);
        info[i].cur_head = tuple.first;
    }
    while (valid_num != 0)
    {
        FindMin(info, 8, &cur_min, &cur_pos);
        memcpy(info[0].blk + info[0].scan_pos * 8,
               info[cur_pos].blk + (info[cur_pos].scan_pos - 1) * 8,
               8);
        if (info[0].scan_pos == 6)
        {
            writeBlockToDisk(info[0].blk, start + j, &buf_write);
            j++;
            info[0].scan_pos = 0;
            info[0].blk = getNewBlockInBuffer(&buf_write);
        }
        else
        {
            info[0].scan_pos++;
        }
        if (info[cur_pos].scan_pos == 7)
        {
            info[cur_pos].valid = 0;
            valid_num--;
        }
        else
        {
            GetTuple(&tuple, info[cur_pos].scan_pos, info[cur_pos].blk);
            info[cur_pos].cur_head = tuple.first;
            info[cur_pos].scan_pos++;
        }
    }
    *IO += buf.numIO;
    *IO += buf_write.numIO;
    freeBuffer(&buf);
    freeBuffer(&buf_write);
}
// merge 8*2=16 sorted blocks from start. (only used for R set)
void Merge_16_R(int start, int *IO)
{
    int i, j = 1;
    int cur_pos, cur_min;
    Buffer buf, buf_write;
    struct Tuple tuple;
    struct MergeInfo info[3]; // use info[0] to store write data.
    int valid_num = 2;
    initBuffer(136, 64, &buf); // 2 blocks is OK
    initBuffer(72, 64, &buf_write);

    info[0].blk = getNewBlockInBuffer(&buf_write);
    info[0].scan_pos = 0;
    info[1].blk = readBlockFromDisk(201, &buf);
    info[2].blk = readBlockFromDisk(209, &buf);
    GetTuple(&tuple, 0, info[1].blk);
    info[1].cur_head = tuple.first;
    GetTuple(&tuple, 0, info[2].blk);
    info[2].cur_head = tuple.first;
    info[1].scan_pos = 1;
    info[2].scan_pos = 1;
    // in this function, use MergeInfo.valid to mark the disk num of 8 blocks.
    info[1].valid = 1;
    info[2].valid = 1;
    while (valid_num != 0)
    {
        FindMin(info, 2, &cur_min, &cur_pos);
        memcpy(info[0].blk + info[0].scan_pos * 8,
               info[cur_pos].blk + (info[cur_pos].scan_pos - 1) * 8,
               8);
        if (info[0].scan_pos == 6)
        {
            writeBlockToDisk(info[0].blk, BASE3 + j, &buf_write);
            j++;
            info[0].scan_pos = 0;
            info[0].blk = getNewBlockInBuffer(&buf_write);
        }
        else
        {
            info[0].scan_pos++;
        }
        if (info[cur_pos].scan_pos == 7)
        {
            if (info[cur_pos].valid == 8)
            {
                valid_num--;
                info[cur_pos].valid = 0;
            }
            else
            {
                freeBlockInBuffer(info[cur_pos].blk, &buf);
                info[cur_pos].valid++;
                info[cur_pos].blk = readBlockFromDisk((cur_pos - 1) * 8 + start + info[cur_pos].valid, &buf);
                info[cur_pos].scan_pos = 1;
                GetTuple(&tuple, 0, info[cur_pos].blk);
                info[cur_pos].cur_head = tuple.first;
            }
        }
        else
        {
            GetTuple(&tuple, info[cur_pos].scan_pos, info[cur_pos].blk);
            info[cur_pos].cur_head = tuple.first;
            info[cur_pos].scan_pos++;
        }
    }
    *IO += buf.numIO;
    *IO += buf_write.numIO;
    freeBuffer(&buf);
    freeBuffer(&buf_write);
}
// merge 8*4=32 sorted blocks from start. (only used for S set)
void Merge_32_S(int start, int *IO)
{
    int i, j = 1;
    int cur_pos, cur_min;
    Buffer buf, buf_write;
    struct Tuple tuple;
    struct MergeInfo info[5]; // use info[0] to store write data.
    int valid_num = 4;
    initBuffer(264, 64, &buf); // 4 blocks is OK
    initBuffer(72, 64, &buf_write);

    info[0].blk = getNewBlockInBuffer(&buf_write);
    info[0].scan_pos = 0;
    for (i = 1; i <= 4; i++)
    {
        info[i].blk = readBlockFromDisk(start + 1 + (i - 1) * 8, &buf);
        GetTuple(&tuple, 0, info[i].blk);
        info[i].cur_head = tuple.first;
        info[i].scan_pos = 1;
        // in this function, use MergeInfo.valid to mark the disk num of 8 blocks.
        info[i].valid = 1;
    }
    while (valid_num != 0)
    {
        FindMin(info, 4, &cur_min, &cur_pos);
        memcpy(info[0].blk + info[0].scan_pos * 8,
               info[cur_pos].blk + (info[cur_pos].scan_pos - 1) * 8,
               8);
        if (info[0].scan_pos == 6)
        {
            writeBlockToDisk(info[0].blk, BASE4 + j, &buf_write);
            j++;
            info[0].scan_pos = 0;
            info[0].blk = getNewBlockInBuffer(&buf_write);
        }
        else
        {
            info[0].scan_pos++;
        }
        if (info[cur_pos].scan_pos == 7)
        {
            if (info[cur_pos].valid == 8)
            {
                valid_num--;
                info[cur_pos].valid = 0;
            }
            else
            {
                freeBlockInBuffer(info[cur_pos].blk, &buf);
                info[cur_pos].valid++;
                info[cur_pos].blk = readBlockFromDisk((cur_pos - 1) * 8 + start + info[cur_pos].valid, &buf);
                info[cur_pos].scan_pos = 1;
                GetTuple(&tuple, 0, info[cur_pos].blk);
                info[cur_pos].cur_head = tuple.first;
            }
        }
        else
        {
            GetTuple(&tuple, info[cur_pos].scan_pos, info[cur_pos].blk);
            info[cur_pos].cur_head = tuple.first;
            info[cur_pos].scan_pos++;
        }
    }
    *IO += buf.numIO;
    *IO += buf_write.numIO;
    freeBuffer(&buf);
    freeBuffer(&buf_write);
}
// make index from start to start+num
void Index(int start, int num, int index_addr, int *IO)
{
    Buffer buf, buf_write;
    struct Tuple tuple;
    unsigned char *blk;
    unsigned char *blk_write;
    unsigned char temp[9] = {0};
    int i, j = 1, k = 0;
    int prev, next;
    int cur_disk = start + 1, cur_pos = 0;
    initBuffer(72, 64, &buf);
    initBuffer(72, 64, &buf_write);
    blk = readBlockFromDisk(cur_disk, &buf);
    blk_write = getNewBlockInBuffer(&buf_write);
    GetTuple(&tuple, cur_pos, blk);
    prev = tuple.first;
    next = prev;
    itoa(prev, temp, 10);
    memcpy(blk_write, temp, 4);
    itoa(cur_disk, temp, 10);
    memcpy(blk_write + 4, temp, 4);
    while (cur_disk != start + num + 1)
    {
        if (j == 8)
        {
            writeBlockToDisk(blk_write, index_addr + k, &buf_write);
            k++;
            j = 1;
            blk_write = getNewBlockInBuffer(&buf_write);
        }
        while (prev == next)
        {
            if (cur_pos == 6)
            {
                cur_pos = 0;
                cur_disk++;
                freeBlockInBuffer(blk, &buf);
                if (cur_disk != start + num + 1)
                {
                    blk = readBlockFromDisk(cur_disk, &buf);
                }
                GetTuple(&tuple, cur_pos, blk);
                next = tuple.first;
            }
            else
            {
                cur_pos++;
                GetTuple(&tuple, cur_pos, blk);
                next = tuple.first;
            }
        }
        prev = next;
        itoa(prev, temp, 10);
        memcpy(blk_write + 8 * (j - 1), temp, 4);
        itoa(cur_disk, temp, 10);
        memcpy(blk_write + 8 * (j - 1) + 4, temp, 4);
        j++;
    }
    if (j > 1)
    {
        writeBlockToDisk(blk_write, index_addr + k + 1, &buf_write);
    }
    *IO += buf.numIO;
    *IO += buf_write.numIO;
    freeBuffer(&buf);
    freeBuffer(&buf_write);
}
int IsRepeat(int *a[], int num, int x)
{
    if (num == 0)
    {
        return 0;
    }
    int i;
    for (i = 0; i < num; i++)
    {
        if (a[i] == x)
        {
            return 1;
        }
    }
    return 0;
}